As a technique for hiding communication data or stored data, there is a common-key block cipher. In the block cipher, data to be encrypted is divided in units, termed block lengths, for encryption. Representative of the block cipher is DES (Data Encryption Standard). In the DES, a structure termed a Feistel structure was adopted for the first time.
FIG. 1 shows the processing for one round of the Feistel structure with a block length of 2n bits. Input data are divided into two n-bit data B1, B2. The data B1 and key data Kr are mashed or stirred with a function F. An exclusive-or (XOR) of output mashed or stirred data and the data B2 is found (B1′). The data B1 is directly to be B2′. B1′ and B2′ are to be inputs to the next round.
In Non-Patent Document 1, a generalized Feistel structure, in which the number of divisions of the Feistel structure is expanded to not less than two, is proposed. This generalized Feistel structure is referred to in the Non-Patent Document 1 as the Feistel-type transformation (FTT). In Non-Patent Document 1, three types of the structures of type-1 to type-3 are proposed. Here, only the type-2 structure is explained. In the following, the ‘generalized Feistel structure’ means the type-2 structure, unless otherwise specified.
FIG. 2 shows a round of the generalized Feistel structure in which input data are divided into a k-number of data, where k denotes an even number not less than 2. Each of the k-numbers of data resulting from the division is termed a ‘string’. This generalized Feistel structure is referred to below as a ‘k-number string generalized Feistel structure’. The one-round processing on the generalized Feistel structure will now be considered as the processing is divided into that by a non-linear transformation unit 20 and that by a permutation unit 21. The non-linear transformation unit 20 directly outputs data Bi of k input data, where i denotes an odd number not larger than k. The non-linear transformation unit also mashes the input data Bi with key data Kj (j=(i+1)/2), by a function F, and XORs the mashed data with data Bi+1 to output the result of the XOR calculations. The permutation unit 21 performs the permutation of cyclic shift of the string data towards left by one string.
Next, the relation between the large/small value of the number of strings k of the generalized Feistel structure and the merit (or the demerit) will be scrutinized. If, in a block cipher with equal block lengths, the number of division k is increased, the size of string data becomes small. For example, in a block length of 128 bits, k=2, n=64. If k=4, n=32 and, if k=8, n=16. If the size of the string data becomes small, the size of processing of the F-function also becomes small. The F-function is the processing that most appreciably influences the implementation scale, such that, if the processing size of the F-function becomes smaller, implementation to a small scale becomes possible to advantage.
On the other hand, if the number of division k is increased, the threat of the cryptoanalytic technique, such as impossible differential attack or saturation attack, increases to disadvantage, in a known manner. It is noted that, to consider detailed cryptoanalysis, it is necessary to take the inner structure of the F-function into account. However, to scrutinize into the influence of the number of strings of the generalized Feistel structure, the F-function is treated here simply as bijective non-linear transformation.
Non-Patent Document 2 shows that the impossible differential characteristics of the generalized Feistel structure with the numbers of strings of 2, 4, 8 and 16 are 5, 9, 17 and 33 rounds. Non-Patent Document 3 shows the impossible differential characteristic of a four-string generalized Feistel structure.
From these results, it is seen that a differential value applied to an input side of the k-string generalized Feistel structure passes through k rounds, while a differential values applied to its output side passes back through k rounds. Since inconsistency occurs at a mid one round, the impossible differential results. Hence, the impossible differential characteristic of 2k+1 rounds persists in the k-string generalized Feistel structure.
The relation between the number of the strings of the generalized Feistel structure and the number of rounds of the saturation characteristics will now be scrutinized. Non-Patent Document 2 states that if, in the case of four strings, total number data are applied along the entire breadth of the string data, there exist six rounds of saturation characteristics from the plaintext towards the ciphertext. Non-Patent Document 2 also states that, since the characteristic may further be extended by two rounds in the direction of the plaintext, there exist eight rounds of the saturation characteristics. In the case of k-strings, the total number data, applied to a given site, becomes diffused or spread to the entire strings after passing through a k-number of rounds. After further passing through three rounds, the data in their entirety become unknown. That is, there exists a k+2 number of rounds of saturation characteristics. In the extension towards the plaintext side, the total number data are diffused to another string after passing back by one round. Hence, the characteristic is diffused as far as (k−1)st string after passing through k−2 rounds. Hence, there exists a 2k-number of rounds of saturation characteristics in the k string generalized Feistel structure.
In the impossible differential attack or the saturation attack, it is attempted to decrypt key data using the above characteristics. The concrete sequence of the impossible differential attack is stated as an example in Non-Patent Document 2. Since routine block cipher attack attempts cryptoanalysis using certain characteristics, the cipher becomes weaker the greater the number of rounds of the characteristics. Thus, in order for the cipher to be strong against such cryptoanalysis, larger numbers of rounds of encryption are necessary. If conversely it is possible to reduce the number of rounds of the characteristics, it becomes possible to secure safety with a smaller number of rounds.    Non-Patent Document 1: Y. Zheng, T. Matsumoto, H. Imai, “On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses,” CRYPTO 1989, LNCS vol. 435, pp. 461-480, Springer-Verlag, 1990.    Non-Patent Document 2: Yukiyasu Tsunoo, Etsuko Tsujihara, Hiroki Nakashima and Hiroyasu Kubo, “Impossible Differentials for Two Types of Extended Feistel Structure,” 2007 Cipher and Information Security Symposium, Jan. 23, 2007.    Non-Patent Document 3: Sony Cooperation, “The 128-bit Blockcipher CLEFIA Security and Performance Evaluations Revision 1.0,” Jun. 1, 2007.